\documentclass[a4paper, english, 10.5pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{babel}
\usepackage{libertine}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{algpseudocode}

\addtolength{\hoffset}{-2cm}
\addtolength{\textwidth}{4cm}
\addtolength{\voffset}{-2cm}
\addtolength{\textheight}{4cm}

\title{\textsc{id}2210 - Project report}

\author{Théo \textsc{Chamley} \and Pierre \textsc{Labiausse}}

\begin{document}

\maketitle

\section*{Warm up: Cyclon's behavior}
For this section (as well as for every following section) the period between two consecutive snapshots has been adjusted to correspond to the period between two successive rounds of the underlying algorithms in order to gather more detailed data, as the convergence speeds for the diverse algorithms are fairly high.

The scenario 2 has been used to produce the following data (available in their raw form in report/cyclon/cyclon.out), that is one node is added to the system, then 30 nodes join 2 seconds later and then 12 nodes join also 2 seconds later for a total of \textbf{43 nodes} over a bootstrap period of 4 seconds (or 4 rounds).

\subsection*{Average in-degree distribution}
As seen in Figure~\ref{fig:indegree}, the average in-degree distribution over the run of the simulation is consistent with the data available in the paper describing Cyclon as this average grows toward the size of the cyclon view for the nodes. If we take the 100th round of the algorithm as an example, we have an average in-degree of 9,6962, with a fairly high standard deviation (2,7195) and the distribution seen in Figure~\ref{fig:indegree_distribution}. This is to be expected, and should not cause a load balancing problem, as the nodes with high in-degrees should rapidly change over time.

\begin{figure}[!h]
\centering
\subfigure[Average of in-degree distrbution over time]{
\includegraphics[scale=0.61]{cyclon/in-degree.pdf}
\label{fig:indegree}
}
\subfigure[In-degree distribution for the 100th round]{
\includegraphics[scale=0.61]{cyclon/in-degree_distribution.pdf}
\label{fig:indegree_distribution}
}
\caption{In-degree information}
\end{figure}


\subsection*{Average path length and diameter}
After an erratic start due to the boot strap period, both the average path length --- Figure~\ref{fig:path_length} --- and the diameter of the graph --- Figure~\ref{fig:diameter} --- decrease rapidly to their stable values (respectively 1.8 and 3). The diameter takes longer before decreasing, as it is not unlikely that a long path between two nodes ``resists'' to the algorithm. Once this long path disappear on the other hand (e.g. if the two vertices at the extremities of this path exchange their view), the diameter reaches its stable value at once.

\begin{figure}[!h]
\centering
\subfigure[Average path length in the graph]{
\includegraphics[scale=0.61]{cyclon/path_length.pdf}
\label{fig:path_length}
}
\subfigure[Diameter of the graph]{
\includegraphics[scale=0.61]{cyclon/diameter.pdf}
\label{fig:diameter}
}
\caption{Path-length \& diameter}
\end{figure}

\subsection*{Clustering coefficient}
This figure (Figure~\ref{fig:clust_coef}) is also similar to the figures of the paper concerning the evolution of the clustering coefficient while using Cyclon: A quick convergence down toward its convergence value (which is around 0.4 in our case). This is much higher than the results obtained in the paper, but it is due to a much lower ratio between the number of nodes in the system and the view size of the nodes in our experiment.

\begin{figure}
\centering
\includegraphics[height=6cm]{cyclon/clust_coef.pdf}
\caption{Evolution of the cluster coefficient}
\label{fig:clust_coef}
\end{figure} 


\section{Task one: Aggregation algorithm}

\subsection*{Implementation notes}
Every time a node receives a set of nodes from the cyclon layer, it picks a random peer in this set, and sends an \textsc{AggregationRequest} to it, along with its value. When receiving an \textsc{AggregationRequest}, a peer sends back an \textsc{AggregationResponse} with its own value, and then updates this value by taking the average of the received value and its own. When receiving an \textsc{AggregationResponse}, the node having initiated the exchange updates its value as well.

The Snapshot class knows the theoretical average bandwidth at all nodes of the system, to calculate the percentage of node having estimated the right value (with error bounds of 1 and 0.1). 

\subsection*{Scenario used}
We chose the following scenario to test our algorithm: the 100 nodes are divided in 5 groups, having for value 5, 30, 80, 90 and 125. In every simulation we ran we had 4 or 5 nodes that always received empty views from the cyclon layer, supposedly because of an original disconnection from the system during the bootstrap process. A couple nodes also received 0 as their value during their initialization. This impacts the interpretation of the data (available in their raw form in report/aggregation/aggregation.out) and appears well in the plot of the estimate of each node at the 100th iteration (Figure~\ref{fig:it100}): every node apart from these four nodes has the same estimate, corresponding to the theoretical average adjusted to take the ``faulty'' nodes into account.

On Figure~\ref{fig:estimated}, we can see that the fraction of nodes estimating the average correctly rapidily converges toward its maximum value (at iteration 14 for a margin of 1 and iteration 18 for a margin of 0.1), even if the curves have some setbacks along the way (when a node estimating the average correctly exchange its value with an incorrect node), but these setbacks are fairly small.

Finally, Figure~\ref{fig:deviation} shows that the standard deviation of the estimates quickly reaches its minima, that is estimates come closer to each other rapidly with rounds of the algorithm. The high value of this minima is due to the ``faulty'' nodes, whose value are fixed (either at their initial values, or at zero).

\begin{figure}[!h]
\centering
\subfigure[Fraction of nodes estimating the average correctly over time]{
\includegraphics[scale=0.61]{aggregation/estimated_correctly.pdf}
\label{fig:estimated}
}
\subfigure[Standard deviation of the estimates]{
\includegraphics[scale=0.61]{aggregation/deviation.pdf}
\label{fig:deviation}
}
\subfigure[Peer's estimates at iteration 100]{
\includegraphics[scale=0.61]{aggregation/estimates_it100.pdf}
\label{fig:it100}
}
\caption{Statistics for Aggregation}
\end{figure}


\section{Task two: T-Man}
\subsection*{Ring overlay}
To construct the ring overlay, each node maintain a T-Man view of size 6 sorted by distance to this node and alterning between a node after and a node before itself on the ring. The successor is in that case the first element of this view, and the predecessor is the second element. With a 100-node scenario, we can see that the ring (and the reverse ring) stabilize very quickly (see Figure~\ref{fig:ring}).

\begin{figure}[!h]
\centering
\includegraphics[scale=0.61]{tman/succ_pred.pdf}
\caption{Number of wrong successors/predecessors in the ring overlay}
\label{fig:ring}
\end{figure}

\subsection*{Small-world overlay}
We chose to implement a finger table on the following model: each node p maintain 12 fingers (as the ID space of the nodes is $2^{13}$), and the $i^{th}$ finger of p is the closest known node to $p+2^i$. You can observe in the raw data (see file report/tman/tman.out) that this works well. Unfortunately, it is difficult to represent this result in a graph.

\section{Task three: Scribe}

\subsection*{Implementation notes}
The way the rendez-vous node was selected in order to publish an event had to be modified to comply with the specifications provided in the assignment (the rendez-vous node being the closest node to the topic ID, and \textit{not} the closest node following this ID, as it was previously done in the class ScribeSimulator).

Each node keeps a Map linking a topic ID to a list of children for this topic. If a node is contacted with a \textsc{ScribeJoinRequest}, it adds the sender to the list of children for the given topic ID. If the topic ID is not previously known to the new parent, it then joins the same topic as well. If, when trying to join a topic, a node is the closest node to the topic ID it knows of, it becomes the rendez-vous node for this topic (formalized only for verification purposes in Snapshot, otherwise no action in necessary for a node to be promoted rendez-vous node).

\subsection*{Results}
Nodes only subscribe to their topics after a given number of T-Man rounds (30 here), in order to let the system become stable. Then the publish event is called, 50 rounds after the bootstrap period is finished. Raw data is available in report/scribe/scribe.out.

As seen on Figure~\ref{fig:scribe_hitRatio}, all nodes interested in one of the published topic receive an notification of the publication event. Moreover, they all receive this notification within 2 rounds of the underlying algorithms (i.e. 2 seconds), and the majority of the nodes receive a notification within 1 round.

Figure~\ref{fig:scribe_spamRatio} is about the efficiency of the protocol in terms of messages. This distribution has a median of 50 and an upper quartile of 60. That means that half the nodes have to handle one notification or more that do not interest them for each notification that does. This is also pointed out in the Scribe paper, and is the price to pay for scalability and load balancing.

\begin{figure}[!h]
\centering
\subfigure[Hit ratio]{
\includegraphics[scale=0.61]{scribe/hitRatio.pdf}
\label{fig:scribe_hitRatio}
}
\subfigure[Spam ratio]{
\includegraphics[scale=0.61]{scribe/spamRatio.pdf}
\label{fig:scribe_spamRatio}
}
\caption{Statistics for Scribe}
\end{figure}

\section{Task four: Overlay optimization}
The goal of this task is to optimize the overlay by taking into account the AS in which the nodes are located. We prefer having a maximum of links inside a same AS to avoid peering, which can be both expensive and slow.

To switch between the optimized and the non-optimized version, you have to change the \texttt{Comparator} used in the \textsc{rankFinger} method of \texttt{tman.system.peer.tman.Tman} (line 275).

\subsection*{Our solution}
To solve this problem, we changed how the rank of a node is calculated in the small-world overlay. Previously, the fingers of a node $p$ pointed to the nodes that were the closest to $p + 2^i$ for $i = 1\dots12$. Now, we look for the closest node in term of ``AS-distance'' in the range $[p+2^i, p+2^{i+1}]$ for $i = 1 \dots 12$. The resulting algorithm is quite simple (the node computing the rank is called $self$):

\begin{algorithmic}
\Function{rank}{i, node}
\If {$node = self$}
    \State \Return $2\cdot MaxDistanceAS$
\ElsIf {$node.id \in [self.id + 2^i, self.id + 2^{i+1}]$}
    \State \Return $asDistance(self, node)$
\Else
    \State \Return $MaxDistanceAS + asDistance(self, node)$
\EndIf
\EndFunction
\end{algorithmic}
Note: The $i^{th}$ finger is chosen as the one having the lowest rank for this particular $i$.

\subsection*{Rationales}
The rationales of this ranking function are twofold:
\begin{itemize}
	\item If we don't know about any node in the right chunk of IDs, we then choose a finger node as close as possible to us in terms of AS
	\item If on the other hand we learn about a node in the right ID chunk, this node would automatically replace a node in the wrong ID chunk, or a node in the right ID chunk farther away from us in terms of AS.
\end{itemize} 

We chose to modify only the finger pointers to preserve the connectivity provided by the ring pointers.
%We can see in this algorithm that the $i^th$ finger will be the one in the range $[p+2^i, p + 2^{i+1}]$ with the lowest AS distance from $p$.

\subsection*{Results}
As we can see on the figure~\ref{fig:asdist}, our algorithm implies a significantly lower AS distance, meaning that the nodes are linked to nodes that are ``geographically'' closer. However, it must be noted that using the provided library consumes a lot of memory and a lot of CPU-usage, significantly slowing down the algorithm.

\begin{figure}[!h]
\centering
\includegraphics[scale=0.8]{tman/as_dist.pdf}
\caption{Average AS distance}
\label{fig:asdist}
\end{figure}

\end{document}

